package leetCode;

import java.util.Arrays;
import java.util.Scanner;

/*

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，
每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

7
3
1 15 7 9 2 5 10

15 15 15 9 10 10 10

0 1 



11
4
1 4 1 5 7 3 6 1 9 9 3

5 5 5 5 7 9 9 9 9 9 9


用递推思想解决
问题要求数组n个数分割后的最大和，我们不必考虑如何分割，只需找到递推方程，化解为子问题即可。
[x,x,x,x,x,x][i-k ~ i]，m属于[i-k, i]
maxSum[i] = maxSum[i-m] + max * m

 */

public class Solution1043 {
    
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] maxSum = new int[n];
        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = i; j > i-k && j >= 0; j--) {
                System.out.println(arr[j]);
                max = Math.max(max, arr[j]);
                maxSum[i] = Math.max(maxSum[i], (j == 0 ? 0 : maxSum[j-1]) + max * (i-j+1));
            }
        }
        // System.out.println(Arrays.toString(maxSum));
        return maxSum[n-1];
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        Solution1043 s = new Solution1043();
        System.out.println(s.maxSumAfterPartitioning(arr, k));

    }

}
